\documentclass[11pt]{article}

\input{preamble.tex}
%\newcommand{\F}{{\mathbb{F}}}
%\usepackage{psfig}
\usepackage{amsmath,amssymb,amsfonts}
\usepackage{graphicx}
\usepackage{fullpage, color}

\newcommand{\RS}{\text{RS}}
\newcommand{\Vol}{\text{Vol}}
\renewcommand{\wt}{\text{wt}}
\renewcommand{\Pr}{\mbox{Pr}}

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in

\begin{document}

\lecture{16}{Oct 11, 2012}{Elena Grigorescu}{Stephanie Oh and Jacques Pienaar}


Today: \begin{itemize}
\item Singleton bounds
\item Gilbert-Varshamov bound
\item Good codes from expanders
\end{itemize}

\section*{Singleton Bounds}
\begin{definition}[Reed-Solomon (RS) code] Let $\F_q$ be a field of order $q$ and $k \leq n$.
        Then $\RS_{q, n, k}$ is a family of codes constructed as follows 
        \begin{itemize}
                \item Pick $n$ distinct elements, say $\alpha_1, \ldots, \alpha_n \in \F_q$;
                \item The encoding maps messages in $\F_q^k$  to codewords in  $\F_q^n$ as follows. For a message $(m_0, \ldots, m_{k-1})$, let $m(x) = \sum_{i = 0}^{k-1} m_i x^i$. Then our code is  
                \[
                        C = \{(m(\alpha_1), \ldots, m(\alpha_n)) \mid m\in \F_q^k [x]\}
                \]
        \end{itemize}
\end{definition}
Another way to represent our set of codes is by defining the generator matrix $G$ as follows:
\[
        G = \begin{pmatrix}
        1 & 1&\cdots & 1 \\
        \alpha_1 & \alpha_2 & \cdots & \alpha_n \\
        \vdots & \vdots & \ddots & \vdots \\
        \alpha_1^{k-1} & \alpha_2^{k-1} & \cdots & \alpha_n^{k-1}
        \end{pmatrix}
\]
then the set of codewords is 
\[
C = \{c \mid \exists m \in \F_q^k, c = m\cdot G\}.
\]

\begin{proposition}
$\Delta(\RS_{n,k,q}) = n-k+1$
\end{proposition}

\begin{proof}
By the following two lemmata we are done.
\end{proof}

\begin{lemma}[Singleton Bound]\label{lemma_sbd}
If $C$ is an $(n,k,d)_q$ code then $d \leq n-k+1$.
\end{lemma}

\begin{proof}
\begin{figure}[ht]
        \centering
        \includegraphics[width=0.8\textwidth]{projection}
        \caption{Projection used in proof of Lemma~\ref{lemma_sbd}.}\label{fig_project}
\end{figure}

Let $C$ be a $(n,k,d)_q$ code. Then it has $q^k$ codewords of length $n$. Project $C$ to a $k-1$ dimensional space by only considering the first $k-1$ entries of each code words (see Figure~\ref{fig_project}). There are at most $q^{k-1}$ possible strings of length $k-1$ in $\F^{k-1}_q$. However, we have in total $q^k$ code words so there must exist at least two codewords with the same projections. Thus the distance between these two code words is $n-(k-1)$. Hence $d \leq n-(k-1) = n-k+1$. 
\end{proof}

\begin{lemma}
$\Delta(\RS_{n,k,q}) \geq n-k+1$.
\end{lemma}

\begin{proof}
Let $(m(\alpha_1), \ldots, m(\alpha_n)) \in\RS_{n,k,q}$. As $\RS$ is a linear code, $\Delta(\RS)$ is equal to the minimum weight codeword. We can thus compute $\Delta(\RS)$ using the relationship
\[
        \Delta(\RS) = n-\max \{\#\alpha_i : m(\alpha_i)=0\}.
\]
So we must ask: what is the maximum number of $\alpha_i$'s such that $m(\alpha_i) = 0$?

Recall $m(x) = \sum_{i = 0}^k a_ix^i \in \F_q[x]$ is a single variable polynomial of degree $k-1$, hence $m(x)$ can have at most $k-1$ roots in $\F_q$. Thus the maximum number of such $\alpha_i$'s is at most $k-1$, and therefore $\Delta \geq n-(k-1) = n-k+1$.
\end{proof}

\section*{Existence of Good Binary Codes}
\begin{definition}
A family of $(n, k_n, d_n)_q$-codes $C = \{C_n\}_{n \rightarrow \infty}$ is \emph{good} if $\exists R, \delta >0$ such that $R_n = k_n/n > R$ and $\delta_n = d_n/n > \delta$ for all $n \geq n_0$ for some $n_0$. 
\end{definition}

In the previous section we have shown that for $\RS_{n,k,d}$, $d = n-k+1$,  $R = k/n$ and $\delta = (n-k+1)/n = 1 - R + 1/n$, hence the Reed-Solomon codes are good codes for $k=\Omega(n)$ (say, for example $k=n/3$). The alphabet of this code is however very large, i.e. $q>n$. In what follows will try and understand binary codes from the perspective of their achievable parameters.

\begin{theorem}[Existence of good binary codes, Gilbert]
Given $\delta > 0$ there exists binary code with rate $R \geq 1-H_2(\delta)$ where $H_2(\delta)$ is the binary entropy\footnote{The binary entropy is a measure of the amount of information in a distribution. It is a lower bound on the average number of bits to describe a distribution optimally.} of $\delta$ defined as 
\[
        H_2(\delta) = -\delta \log_2(\delta) - (1-\delta)\log_2(1-\delta).
\]
Note that $H_2(1/2) = 1$ is the maximum value possible for $H_2$ and $H_2(\delta)=H_2(1-\delta)$.
\end{theorem}

\begin{proof}
An equivalent statement is to show that there exists a code $C = (n,k,d)_q$ such that $|C|=2^k \geq 2^n/{\Vol(d-1,n)}$ where $\Vol(d-1,n)$ is just the volume of an $n$-ball with radius $d-1$. 

We use a greedy algorithm to build the code step by step. 
\begin{enumerate}
\item Let $S = \{0,1\}^n$.
\item Let $C = \emptyset$.
\item While $S \neq \emptyset$ pick $x \in S$ and let $C = C \cup \{x\}$. Now $S = S \setminus B(x, d-1)$. 
\end{enumerate}

\begin{figure}[ht]
        \centering
        \includegraphics[width=0.4\textwidth]{intersect.pdf}
\end{figure}

Clearly, per construction, $\Delta(C) \geq d$. We'll show that $|C|$ satisfies the condition above. (By definition $k=\log |C|$ and so $|C|=2^k$).

Note that $\Vol(S)=2^n$ (before starting adding points to $C$), and for each $x\in C$ if $y\in B(x,d-1)\cap C$ then $x=y$ hence $|C|\Vol(x,d-1)\geq 2^n$, that is
\[
        |C| = 2^k \geq \frac{2^n}{\Vol(d-1, n)}.
\]

To finish the proof we'll show why this statement implies the statement in the theorem.

\begin{claim} $\Vol(pn, n) \leq 2^{H_2(p)n}$, for $p<1/2$.
\end{claim}
\begin{proof}
\begin{align*}
1 &= (p + (1-p))^n = \sum_{i =0}^n \binom{n}{i} p^i (1-p)^{n-i}\\
  &= \sum_{i=0}^n \binom{n}{i} (\frac{p}{1-p})^i(1-p)^n\\
  &\geq \sum_{i =0}^{pn} \binom{n}{i} (\frac{p}{1-p})^i(1-p)^n\\
  &\geq \sum_{i=0}^{pn} \binom{n}{i}p^{pn}(1-p)^{(1-p)n}\\
  &\geq \sum_{i=0}^{pn} \binom{n}{i} 2^{-H_2(p)n}.
\end{align*}
\end{proof}


But $\Vol(pn, n) = \sum_{i=0}^{pn} \binom{n}{i}$. Now $d-1 \leq \delta n$.
So there exists $C$ such that 
\[
        |C| = 2^k \geq \frac{2^n}{\Vol(d-1,n)} \geq \frac{2^n}{\Vol(\delta n,n)} \geq \frac{2^n}{2^{H(\delta n)n}}.
\]
Therefore, $k \geq (1-H_2(\delta))n$ which implies that $R \geq 1-H_2(\delta)$.
\end{proof}

Thus we have shown that there exists a good binary code. Furthermore, Varshamov showed that in fact there exist good linear binary codes.

\section*{Existence of Good Linear Binary Codes}

\begin{theorem}[Varshamov]
There exist linear binary codes $[n,k,d]_2$ with $R \geq 1-H_2(\delta)$. Reformulating,  if $2^k - 1 < 2^n/{\Vol(d-1,n)}$ then there exists a linear binary code $C$ with $|C| = 2^k \geq {2^n}/{\Vol(d-1,n)}$.
\end{theorem}

\begin{proof}
We will use the probabilistic method to show that there exists
$G \in \{0,1\}^{k \times n}$ such that $\forall x \neq 0$, $\wt(x\cdot G) \geq d$ with probability greater than $0$.
\[
        \Pr_G [\text{all $x\cdot G$, $\wt(x\cdot G) \geq d$}] = 1-\Pr_G[\exists\, x, \wt(x\cdot G) \leq d-1].
\]
Let us fix $x \neq 0$. Then 
\[
        \Pr_G[\wt(x\cdot G) \leq d-1] \leq \frac{\Vol(d-1,n)}{2^n}.
\]
So by a union bound then
\[
        \Pr_G[\forall\, x, wt(x\cdot G) \leq d-1] \leq (2^k-1)\frac{\Vol(d-1,n)}{n}<1
\]
Hence, $\Pr_G[\text{all $x\cdot G$, $\wt(x\cdot G) \geq d$}] > 0$. Thus, there exists a $G$ such that $C = \{x\cdot G\}$ has distance at least $d$. 
\end{proof}


To recap and compare,  recall that the Hamming bound says that for all binary codes $R \leq 1-H_2(\delta/2)$. Now we also know by the Gilbert-Varshamov bound that there are codes for which $R \geq 1-H_2(\delta)$. When $\delta$ is a constant then $R$ is constant for these codes and therefore these are good codes.


\begin{figure}[ht]
        \centering
        \includegraphics[width=0.7\textwidth]{rates}
        \caption{Rate bounds of good codes.}
\end{figure}

In the next lecture we'll see how to construct good binary codes from bipartite expander graphs. We briefly now mention how to view a graph as a code.

\begin{figure}[ht]
        \centering
        \includegraphics[width=0.3\textwidth]{adjG}
        \caption{Representing a linear code as a graph.}\label{fig_adjG}
\end{figure}

The idea is to let the adjacency matrix of a bipartite graph (where the rows index left vertices and the columns index the vertices on the right) represent the parity check of a code (see Figure~\ref{fig_adjG}). So $C = \{c \mid c\cdot H = 0\}$ where $c \in \{0,1\}^n$ and $H \in \{0,1\}^{n \times (n-k)}$. Then $L$ consists of $\{1, \ldots, n\}$ and $R$ consists of $\{1, \ldots, n-k\}$ and there exists an edge $(i,j)$ with $i \in L$ and $j \in R$ if in the $j$th column of $H$ there is a $1$ in the $i$th row. Here $R$ is also called the set of constraints and $L$ is the set of variables. Then you can see that $H$ is simply the adjacency matrix of $L \cup R$. Then we can think of a code $C = \{c \mid c \text{ satisfies all of the constraints}\}$, where a constraint is satisfied if the sum of all adjacent bits are $0$ (i.e. the vertex representing the constraint is adjacent to an even number of variables set to $1$.

\end{document}
